The present invention relates generally to computerized information systems. More specifically, it describes sophisticated techniques for managing, locating, allocating and assuring the availability of information resources in a distributed environment.
Distributed applications are much more difficult to write and manage than applications developed for a single computer. The basic problem facing distributed application designers is not a lack of resources but an inability to dynamically manage and effectively leverage those resources. Efficiently utilizing a multiplicity of resources often becomes a prohibitively complex problem.
The availability of an application on demand is of critical importance in many operational environments. In a distributed environment, it is possible to enhance the availability and fault-tolerance of an application by providing redundant points of service in order to ensure that the failure of any individual part of the network does not prevent the network, as a whole, from delivering critical services. However, the introduction of redundant points of service raises a set of secondary issues that are addressed by distributed application designers. First, one must consider the manner in which the application leverages redundant resources so as to decrease the response time of a given service provider when this provider is under load. One must also consider the number of service points which will be sufficient to accommodate demand, as well as the physical locations at which these service points should be located.
Many prior art approaches make no attempt whatsoever to leverage redundant resources so as to decrease the response time of a given service provider under load. Instead, alternate service instances of a given resource are held in reserve and exist solely to provide fault-tolerant service provision. The primary advantage of this simplistic approach is that the backup instances of service have predictable levels of performance. However, this method is inefficient. Redundant resources which are idle are maintained and upgraded, but bring no benefit other than increasing the odds that a service can tolerate the failure of a given service provider.
Other prior art techniques do provide for the leverage of resources. One example of such a technique is known as xe2x80x9cearly bindingxe2x80x9d. Service requestors are statically assigned instances of service provision, which is advantages in that requests for service are spread across multiple instances of a given service provider. Service requests are then assigned to a specific instance of a service provider before invocation. Since requestors are xe2x80x9cearly-boundxe2x80x9d to service provision, the method does not require the performance of successive iterations in an attempt to locate a suitable service provider. However, a major shortcoming of the xe2x80x9cearly bindingxe2x80x9d approach stems from the static binding that occurs between a request for service and the service provider. This method is not able to adjust to any shifts in the population or state of service providers. A failure in an individual instance of a service provider denies access of that service to the population of requestors it services. Moreover, the allocation of requests cannot respond to varying loads. If a community of service requestors is very active, the system does not spread the demands across all available providers. Only those providers statically bound to the requestors are used to process the workload created by the incoming requests.
Another existing technique for leveraging redundant resources is termed xe2x80x9clate bindingxe2x80x9d. Service requestors are dynamically assigned to a given instance of a given service provider. The dynamic assignment of a service request to a service provider requires that the system decide which candidate service provider should process a given request. This decision is made by employing any of three strategies:
(i) Round Robin: incoming service requests are assigned to a list of candidate service providers by a dispatching entity. Selection of candidates is determined by the order of the candidates on the list. Each service provider receives a service request in turn.
(ii) Random Binding: similar to the Round Robin method, except that the list of candidate service providers has no particular order. Assignment of service provisions is drawn from the list of candidates at random.
(iii) Policy Driven: the dispatching entity examines incoming service requests and applies a set of policies that influence the dynamic assignment of requests to service providers.
The Round Robin and Random Binding strategies make the assignment of service requests to service providers using a blind algorithm. They do not take into consideration the demand or load on system resources. Policy-driven algorithms distribute service requests based on a set of rules. The system reports a set of xe2x80x9cmetricsxe2x80x9d to a rule engine. The rule engine uses these metrics to make decisions regarding the allocation of system resources to satisfy service requests.
The problem with policy-based algorithms is that they create bottlenecks in the dispatching entity. The overhead associated with the gathering of data and the interpretation of that data is often intensely resource consuming. More importantly, because service providers require different sets of resources from different locations and in different ratios, the policies created for one class of service provision are not applicable to other service providers. Taken together, these factors result in a direct relationship between the complexity of the dispatching entity and the number of services being managed.
Prior art techniques have also been developed to determine the quantity of service points which are sufficient to accommodate demand. Distributed applications attempt to spread requests for service across a population of candidate service providers. In its simplest form, the response time for a provision of service ought to decrease as the population of service providers increases. Distributed application architects take a specification of maximum acceptable response time and an estimation of projected load, and then commission resources to meet that demand. They guess at the amount of resources they should assign to a given problem, and tune this estimate over time through observation.
The task of estimating and refining resource allocation estimates and bringing additional resources on-line (or off-line) is labor intensive. Moreover, each time the demand, resource, or priority profiles of a network change, the allocation of resources should be adjusted. The man-hours required to dynamically tune resources allocation in a distributed environment are prohibitive.
Pursuant to one common prior art approach, the management of access to system resources in a distributed environment may be conducted by ascertaining the rights and privileges of a service requestor at the time that a service request is received. If a requestor""s privileges are sufficient to allow execution of the request for service provision, the request proceeds. Requestors with insufficient privileges are not granted access to a service. Using this approach, access to a system resource is binary: based upon the identity of the service provider, the request is either granted or not granted. Access privileges to system resources are typically defined and assigned by an administrator. The administrator grants these privileges to requesting entities in an effort to anticipate access requirements in advance of actual service requests. While this method of access control is well-suited to the provision of system security, it is deficient when applied to resource allocation. The assignment of privileges to regulate access to resources is essentially an effort to early-bind the set of resources to a service requestor. Such an assignment shares the same set of design deficits as the early binding technique described above.
As a consequence of the limitations of the foregoing resource allocation techniques, it has become common practice to:
(i) Allocate resources to satisfy hypothetical peak demands, thereby guaranteeing that, for those times that the system is not operating at peak demand, a portion of the allocated resources are idle;
(ii) Postpone efforts to improve slow service provider response times. Often, the response times can be decreased by the reallocation of resources. However, because organizations lack the man-hours to actually configure the population of service providers, this work is typically postponed until time permits; and/or
(iii) Dedicate network resources to performing a specific task. This leads to inefficient resources allocation under anything but the expected load conditions. In addition, this causes even more network resources to remain idle under normal load.
Other prior art approaches have dealt with selecting appropriate physical locations for applications on a network so as to enhance system performance. The physical location of an application on a network directly impacts the response time of that application. Services installed on under-utilized resources execute faster than identical services installed on busy resources. The topological proximity of a service to its potential requestors and the proximity of system resources necessary for the delivery of that service directly affect the response time of that service. Ideally, the decision of where an instance of a service ought to be installed takes into account the location of the community of service requestors, available bandwidth, the proximity of data and third party services, and the load on the server where the services run. At present, this decision is typically made by system administrators and is adjusted as new applications, resources and demands are made of the system. Unfortunately, as in the case of resource allocation, decisions pertaining to resource location are also labor-intensive and subject to similar constraints. However, the locations of system resources, service providers, and service points are not readily changeable so as to provide for optimization under a variety of conditions. This is compounded by the difficulty associated with gathering statistics and measures to determine if the location of a service is inefficient and if so, where to relocate the service in order to maximize efficiency.
In view of the deficiencies of the prior art, it is an object of the invention to provide a dynamic mechanism for managing, organizing, and allocating service providers in the operational environment of a computer network.
It is a further object of the invention to apply market economic methods to the management, organization, and allocation of service providers.
It is a still further object of the invention to apply trade and price mechanisms to a plurality of local resource allocation decisions, and to merge these decisions into resource allocation rules which efficiently manage service provider usage in large computer networks.
It is another object of the invention to dynamically allocate service providers based upon the supply of the providers and the demand thereof.
It is moreover another object of the invention to utilize only locally available information to perform global optimization of service provision.
It is yet another object of the invention to provide a real-time service provider allocation scheme that adaptively responds to ever-changing system conditions.
It is a further object of this invention to permit system administrators to influence the utilization of selected service providers through the use of price surcharges.
In accordance with the objects of the invention, one or more service providers are allocated according to the relative priorities of processes which request the use of a respective service provider. A service provider may refer to a database, a computer program, a person providing services over a computer network, an information resource, or a hardware resource such as a fax machine, a printer, or a data storage drive. A process refers to the manner in which any entity that can request the allocation of a service provider will use that service if it is, indeed, allocated to that entity. A service requestor refers to an entity that may require the use of one or more service providers. Illustrative service requestors include computer programs as well as devices coupled to the computer network for use by individuals requesting services.
A plurality of service providers, a plurality of service requestors, and a service broker are all accessible from a computer network. The service broker uses a service provider allocation directory to allocate service providers to service requestors based upon dynamically-changing pricing constraints.
The service provider allocation directory associates each of a plurality of service providers with a set of representative indicators. A first indicator identifies a type or class description of the service provider. A second indicator specifies the location of the service provider on the computer network. A third indicator specifies the base price from the service provider which includes the cost of underlying services. The service provider allocation directory may also utilize one or more of the following optional indicators. For instance, the service provider may provide one or more attribute prices, which are all entered into the service provider allocation directory as a fourth indicator. The attribute prices specify the price differential for different levels of service or options that the service provider has available. A fifth indicator may specify the load premium as provided by the execution manager. The load premium reflects the demand on a given service provider by the service requestors. Increased demand causes the premium to increase. Decreased demand causes the premium to gradually decrease. A sixth indicator may specify the reputation premium as provided by the execution manager. The reputation premium is used as an adjustment to direct requests away from service providers that have a history of failure or not fulfilling service requests. Each failure to complete a request causes a proportional increase in the reputation premium. A seventh indicator may represent an administrative premium which can be utilized by the system administrator to influence system usage to or away from a service provider.
Service requestors issue service requests over the computer network. The service request includes the type or class of service desired, as well as a budget specifying the maximum price that the service requestor will pay for that service. Service requests are allotted request budgets which are representative of the relative value the users of the invention place on the timely execution of a service request. Higher request budgets allow the service requestor to purchase higher execution priority from a service provider, thereby providing a more timely execution of the service request. Moreover, the service requestor will allocate a higher percentage of its total budget to individual service requests having higher business value. In this fashion, service requests with high business value, as expressed by their budget, gain prioritized access to the invention""s resources.
Service providers send availability messages to the service broker indicating the availability of one or more services. These messages identify the type or class of service, the location of the service, and associate each service with a base price and attribute prices. The broker stores these availability messages in the service provider allocation directory. The execution manager sends execution premium messages to the service broker indicating new, updated values for the reputation and load premiums. The broker stores the execution premiums in the service provider allocation directory.
In response to the receipt of a service request, the service broker uses the indicators in the service provider allocation directory to generate a trial candidate list of service providers. This trial candidate list includes only service providers of the type or class desired by the service requestor. The service broker then calculates a levied price for each of a plurality of service providers on the trial candidate list. The levied price is the summation of the base price, requested attribute price, load premium, reputation premium, administrative premium and a delivery premium that is determined based on the relative locations of the service requestor and the service provider.
The service broker eliminates any service providers on the trial candidate list that do not have a levied price below the budget specified in the service request, thus providing a final candidate list. The service broker then generates a draft contract for each service provider on the final candidate list. The draft contract specifies the identity of the service provider, the location of this service provider on the computer network, the identity of the service requestor, the location of the service requestor on the computer network, the levied price, the base price, the attribute price, the load premium, the reputation premium, the administrative premium, the delivery premium, the type or class of service, an optional schedule for performance of the service, and an optional contract expiration date and time.
In response to the receipt of one or more draft contracts, the service requestor may choose to redeem any of these draft contracts through the use of an execution manager software component accessible from the computer network. However, it is usually the lowest-priced draft contract that is redeemed. The execution manager directs the execution of a service request contract, and instructs the accounting manager to collect the funds from the service requestor to make payments to the service provider. Every service provider and service requestor in the system has an associated account that describes the funds at the service provider or service requestor""s disposal. These funds are used as a medium of exchange between service provider and service requestor. Upon the successful delivery of service the accounting manager extracts funds from the service requestor account and moves them to the service provider account in the amount of the sum of the base price, the attribute price and the load premium specified in the redeemed contract. In this manner the account associated with the service provider gains funds.
Service providers are also charged rent. Rent is defined as a periodic charge against a service provider account. The rent is determined by the summation of all levied prices for all software and hardware components needed to actively maintain the service provider, even while it remains idle. In this manner, the rent and therefore the account level, are directly related to the speed, capacity and demands associated with the physical hardware, for example, memory, disk storage, and CPU utilization. In this manner, the account associated with a service provider loses funds.
The invention will install additional copies of a service provider on the network when at least one of the following administratively defined thresholds has been surpassed: (1) the account associated with a service provider which provides a record of the successful delivery of service over time; (2) the reputation premium associated with a service provider which provides a measure of the service providers ability to deliver service; (3) the load premium which is a measure of current demand on a service provider. The invention will split the funds associated with the original service provider account between the original service provider and the newly created copy. When a service provider account shrinks past an administratively defined threshold, due to payment of rent and a lack of demand, the service is deemed bankrupt and the service provider is erased from the service provider allocation directory and removed from the network.
Pursuant to a preferred embodiment of the invention, the levied price charged by each service provider is dynamically adjusted over time in accordance with a set of adjustment rules. According to a first rule, as the demand for a particular service provider increases, its levied price also increases. The levied price of a service provider that is idle for too long will be decreased until sufficient demand for the resource is generated. Finally, a given service provider should generate sufficient demand or risk xe2x80x9cbankruptcyxe2x80x9d, meaning that the service provider is removed from the allocation directory. Accordingly, supply and demand are the main driving forces responsible for lowering or increasing levied prices. Profits or losses determine the continued existence of a given service provider or its removal from the service provider allocation directory.
Pursuant to a further embodiment of the invention, strategic load balancing rules are applied to each service provider to dynamically de-install an ineffective service provider, and to dynamically replicate service providers that cannot handle all of the current demand from service requestors. These load balancing rules, as well as any rules used to determine levied prices, need only utilize information that is locally available on the computer network. Such rules need not be based upon global knowledge of the state of the entire computer network. In this manner, the levied prices computed by the service broker, in combination with strategic load balancing, produce a globally adaptive, self-configurable behavior for a plurality of service providers.